
// https://leetcode.cn/problems/word-search/description/

class Solution
{
    int flag = 0;

public:
    bool exist(vector<vector<char>>& board, string word)
    {
        for (int i = 0; i < board.size(); ++i)
        {
            for (int j = 0; j < board[0].size(); ++j)
            {
                if (board[i][j] == word[0])
                    dfs(board, i, j, word, 1);
            }
        }

        return flag;
    }

    void dfs(vector<vector<char>>& board, int x, int y, string& word, int pos)
    {
        if (pos == word.size() || flag)
        {
            flag = 1;
            return;
        }

        char c = board[x][y];
        board[x][y] = 0;

        if (check(board, x - 1, y) && pos < word.size() && board[x - 1][y] == word[pos])
            dfs(board, x - 1, y, word, pos + 1);

        if (check(board, x + 1, y) && pos < word.size() && board[x + 1][y] == word[pos])
            dfs(board, x + 1, y, word, pos + 1);

        if (check(board, x, y + 1) && pos < word.size() && board[x][y + 1] == word[pos])
            dfs(board, x, y + 1, word, pos + 1);

        if (check(board, x, y - 1) && pos < word.size() && board[x][y - 1] == word[pos])
            dfs(board, x, y - 1, word, pos + 1);

        board[x][y] = c;
    }

    bool check(vector<vector<char>>& board, int x, int y)
    {
        if (flag) return false;
        return x >= 0 && x < board.size() && y >= 0 && y < board[0].size();
    }
};